package com;


public class LCS {

	public static void main(String[] args) {
		int[] a = {1, 2, 3};
		int[] b = {1, 2};
		int[][] c = LCSLength(a, b);
		System.out.println(TraceBack(c, a, b, a.length-1, b.length-1));
	}
	
	private static int[][] LCSLength(int a[], int b[]) {
		int[][] c = new int[a.length+1][b.length+1];
		for(int i=0; i<a.length; i++) {
			for (int j=0; j<b.length; j++) {
				if(a[i] == b[j])
					c[i+1][j+1] = c[i][j] + 1;
				else
					c[i+1][j+1] = Math.max(c[i+1][j], c[i][j+1]);
			}
		}
		return c;
	}
	
	private static String TraceBack(int[][] c, int[] a, int[] b, int i, int j) {
		if(a[i] == b[j])
			if(i==0 || j==0)
				return "" + (i==0 ? a[i] : b[j]);
			else
				return TraceBack(c, a, b, i-1, j-1)+" "+ a[i];
		else {
			if(c[i+1][j]>c[i][j+1])
				return TraceBack(c, a, b, i, j-1);
			else
				return TraceBack(c, a, b, i-1, j);
		}
	}
}
